<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html> <head>
<title>The Dining Philosophers</title>
</head>

<body>

<Center><h1>The Dining Philosophers</h1></Center>
<BR>Due: March 8 4:59:59 PM</BR>

<h1>Overview</h1>

<p>In this lab you will implement several variations of the classic
"dining philosophers problem" in order to practice your multi-threaded
programming skills.</p>

<p>As in the classic problem, there are N plates and N chopsticks
arranged around a circular table. There are N philosophers, each of
whom periodically eats.  A philosopher must grab the two chopsticks to
the left and right of his/her plate in order to eat.</p>

<p>In the new problem, the philosophers have become rather worldly
and hired two servants.  At the center of the table there is a bowl
that holds some servings of rice. One servant occasionally refills
the bowl when it is empty. Ocassionally, when the bowl is empty and no one is eating,
the other servant gathers up all of the plates, chopsticks, and the
bowl, cleans the table, and then returns the plates, chopsticks, and
bowl to their places; this cleaning is only done if all philosophers
have eaten at least once since the last cleaning (i.e., all plates are
dirty.)  A philosopher cannot eat if there is no rice to take from the bowl;
nor can a philosopher eat while the chopsticks or plates are being
cleaned. The filling servant cannot fill if the bowl is being
cleaned. The cleaning servant does not clean if anyone is eating, if
the bowl has rice in it, or if the bowl is currently being filled.</p>


<p>Despite this worldly change, a handful of the pilosophers occasionally
reach a state of trancendental bliss during which they can go long
periods of time without eating.</p>

<p>We model philosophers and servers as threads. We maintain all
shared state in a "table "object, and the threads coordinate their
actions via the shared state.</p>

<p>Thus, each philosopher thread acts as follows:</p>

<pre>
while(1){
   table_startEating(table, myId);
   eat();
   table_doneEating(table, myId);
   think();
   if(trancendetal_bliss()){
      longThink();
   }
}
</pre>

<p>The rice servant acts as follows</p>

<pre>
while(1){
   table_takeEmptyBowl(table);
   fill();
   table_returnRefilledBowl(table, servingCount);
}
</pre>

<p>and the cleaning servant acts as follows</p>
<pre>
while(1){
  table_waitUntilAllPlatesDirty(table);
  table_gatherSticks(table); // Only if no one eating and bowl empty
  table_gatherBowl(table);
  table_gatherPlates(table);
  clean();
  table_returnSticks(table);
  table_returnBowl(table);
  table_returnPlates(table);
}
</pre>  

<p>Of course, not even philosophers can get good help these days,
so the cleaning servant may gather and return sticks, bowls, or plates
in any order (e.g., gather sticks, gather plates, gather bowl, return bowl, return plates, return sticks),
though the servant always gathers all of the items before returning any of them.
Your solution should be robust to these minor variations.
</p>

<p>You will implement two variations of the "table" object. The first
implements the standard dining philosophers problem (with no servants).
The second adds the servants
and guarantees fairness among the eaters
and lack of starvation for the servant threads.
</p>

<p>Your solutions must be free of starvation and deadlock. </p>

<H1>Grading</H1>

<p>Testing multi-threaded code is difficult, important, and of limited
effectiveness. As part of your assignment, <b>you must write sanity
check tests and convince yourself that sensible invariants are
maintained.</b> We <b>strongly recommend that you include
many assert() statements in your implementations</b>.</p>

<p>Grading will be based largely on <b>code inspection</b> with an emphasis
on the following points:

<UL>
  <LI> Your solution <b>must</b> adhere to
the multi-threaded coding standards described in class and in <A
HREF="http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/reading/programming-with-threads.pdf">this</A>
handout.  </LI>

  <LI>Your solution should be easy to understand. Easy to understand
  multi-threaded code is much better than confusing multi-threaded
  code even if they both do the same thing.</LI>

   <LI>Your solution <b>must</b> include sanity checks that
  convincingly demonstrate that important invariants are maintained
  (e.g., only one philosopher holds a chopstick at a given time; e.g.,
  a philosopher holds two chopstics to eat; etc. etc. etc.) Part of your job is to
  devise a set of invariants that is convincing -- simple enough for a reader to
  understand and be convinced that they cover the important restrictions
  on this solution.</LI>
</UL>
  
  


<H1> Getting started </H1>

<p>We provide code to help you get started. Download and untar
<A HREF="http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/labs/lab-T-dining.tar">http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/labs/lab-T-dining.tar</A>. Cd
into the directory. <I>Make</I> should work and the test program should
report an assertion failure</p>

<p>We provide a simple library for threads, locks, and condition
variables in sthread.h and sthread.c. Please use this library for this
lab -- it includes some sanity check code to validate some invariants
on how you use locks and condition variables.</p>

<H1>First version</H1>

<p>Implement OBLBasic_Table
 (OBL stands for "One Big Lock"; I had planned on assigning some additional
versions of this problem to explore coarse- v. fine-grained locking but I decided that
a few variations of coarse-grained locking will be enough for now).  For this
version, you do not need to implement "servants" (instead, assume an
always-full bowl), nor do you need to guarantee fairness (e.g., one
philosopher may eat 1000 times while another may eat only 5
times). However, your solution should guarantee freedom from
starvation: assuming a random scheduler that randomly selects a ready
thread to run (with each ready thread having a non-zero probability of
being selected), eventually all philosophers will eat.  </p>

<p>Implement OBLBasic_Table. In the README file, explain how you ensure
freedom from deadlock and starvation and explain your testing strategy.</p>

<H1>Second version</H1>

<p>Implement OBLFair_Table. Include support for the "servants." Also,
your solution should guarantee fairness: (1) if two philosophers are
waiting to eat and both need the same chopstick, then the one who has
been waiting longer will get the chopstick before the other one, (2)
if the rice bowl currently has k servings, then the k philosophers who
have been waiting to eat the longest will eat before any other
philsophers eat, and (3) if all philosophes have eaten since the last
cleaning, and the cleaning servant is ready to clean, the filling
servant will refrain from refilling the bowl until the cleaning is
done.  After cleaning, once the bowl is returned by the cleaning
servant, the filling servant may refill the bowl even if the cleaning
servant has not yet returned the chopsticks or plates.</p>

<p>Implement OBLFair_Table. In the README file, explain how you ensure
fairness, freedom from deadlock, and freedom from starvation and
explain your testing strategy.</p>

<hr>
</body> </html>
